// 给你一个字符串 s，找到 s 中最长的回文子串。

// 示例 1：

// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
// 示例 2：

// 输入：s = "cbbd"
// 输出："bb"


/**
 * 这是最长回文子串
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
    const n = s.length;
    let dp = new Array(n).fill(false).map(() => new Array(n).fill(false));
    
    let res = 0;
    let left = 0, right = 0;

    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j]) {
                if (j <= i + 1 || dp[i + 1][j - 1])
                    dp[i][j] = true;
            }
            if (dp[i][j] && j - i + 1 > res) {
                res = j - i + 1;
                left = i;
                right = j;
            }
        }
    }
    return s.substring(left, right + 1);

};







/**
 * 这是516.最长回文子序列
 * @param {string} s
 * @return {number}
 */
// var longestPalindrome = function (s) {
//     const n = s.length;
//     let dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

//     for (let i = 0; i < n; i++)
//         dp[i][i] = 1;
    
//     for (let i = n - 1; i >= 0; i--) {
//         for (let j = i + 1; j < n; j++) {
//             if (s[i] === s[j]) {
//                 dp[i][j] = dp[i + 1][j - 1] + 2;
//             } else {
//                 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
//             }
//         }
//     }
//     return dp[0][n - 1];

// };